{\magonebf 4.4 Dictionary Arrays (d\_array)}

\decltwo d\_array I E 

{\bf 1. Definition}

An instance $A$ of the parameterized data type \name\ (dictionary 
array) is an injective mapping from thelinearly ordered data type $I$, called 
the index type of $A$, to the set of variables of data type $E$, called the 
element type of $A$. 

\bigskip
{\bf 2. Creation}

a) \create A (x)

b) $\_d\_array${\tt <}$I,E,impl${\tt >} $A(x)$ ;

creates an injective function $a$ from $I$ to the set of unused variables of 
type $E$, assigns $x$ to all variables in the range of $a$ and initializes $A$
with $a$. Variant a) chooses the default data structure (cf.~4.4.5), and 
variant b) chooses class $impl$ as the implementation of the dictionary 
(cf.~section~9 for a list of possible implementation parameters).


\bigskip
{\bf 3. Operations}

\+\cleartabs & \hskip 1.8truecm & \hskip 5truecm &\cr
\+\opa E\&   {I\ x}  
                      {returns the variable $A(x)$}
\smallskip
\+\op bool   defined {I\ x}
                      {returns true if $x \in dom(A)$, false otherwise; here}
\+\nop                {$dom(A)$ is the set of all $x\in I$ for which $A[x]$ has}
\+\nop                {already been executed.}

\bigskip
{\bf 4. Iteration}

{\bf forall\_defined}($x,A$) 
$\{$ ``the elements from $dom(A)$ are successively assigned to $x$'' $\}$


\bigskip
{\bf 5. Implementation}

Dictionary arrays are implemented by randomized search trees ([AS89]). 
Access operations $A[x]$ take time $O(\log dom(A))$.
The space requirement is $O(dom(A))$.


\vfill\eject
{\bf 6. Example}
\bigskip
\input prog/d_array.prog

